home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / source / src / basic / _olist.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-11-16  |  6.5 KB  |  387 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  _olist.c
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16. #include <LEDA/impl/olist.h>
  17. #include <ctype.h>
  18.  
  19. #define SWAP(a,b) { register obj_link* x = *a; *a = *b; *b = x; }
  20.  
  21. #define MIN_D 16 
  22.  
  23. //------------------------------------------------------------------------------
  24. // Members of class obj_list
  25. //------------------------------------------------------------------------------
  26.  
  27. obj_list::obj_list()      
  28. { h = nil; 
  29.   t = nil;
  30.   count = 0;
  31. }
  32.  
  33. void obj_list::clear()
  34. { h = nil;
  35.   t = nil;
  36.   count = 0;
  37.  }
  38.  
  39.  
  40. obj_link* obj_list::get_item(int i) const
  41. { obj_link* p = h;
  42.   while ( p && i--) p = p->succ_link; 
  43.   return p;
  44. }
  45.  
  46. obj_link* obj_list::succ(obj_link* p, int i)  const
  47. { while ( p && i--) p = p->succ_link; 
  48.   return p;
  49. }
  50.  
  51. obj_link* obj_list::pred(obj_link* p, int i) const
  52. { while ( p && i--) p = p->pred_link; 
  53.   return p;
  54. }
  55.  
  56.  
  57. int obj_list::rank(obj_link* x)   const   /* rank by linear search */
  58. { obj_link* p = h;
  59.   int r = 1;
  60.   while ( p && p != x) 
  61.   { p = p->succ_link; 
  62.     r++;
  63.    }
  64.   return (p) ? r : 0;
  65. } 
  66.  
  67.  
  68. obj_link* obj_list::insert(obj_link* n, obj_link* l, int dir) 
  69. { 
  70.   if (dir==0) //insert after l
  71.     return insert(n,l);
  72.   else //insert before l
  73.     { obj_link* p=l->pred_link;
  74.       n->pred_link = p;
  75.       n->succ_link = l;
  76.       l->pred_link = n;
  77.       if (l==h) h=n;
  78.       else p->succ_link = n;
  79.       count++;
  80.       return n;
  81.     }
  82. }
  83.  
  84.  
  85. void obj_list::conc(obj_list& l)
  86. { if (t) { t->succ_link = l.h;
  87.           if (l.h) { l.h->pred_link = t; t = l.t; } }
  88.    else { h = l.h; t = l.t; }
  89.  count = count+l.count;
  90.  l.h = l.t = 0;
  91.  l.count = 0;
  92. }
  93.  
  94.  
  95. void obj_list::split(obj_link* p, obj_list& l1, obj_list& l2)
  96. { 
  97.   l1.clear();
  98.   l2.clear();
  99.  
  100.   if (p==nil)    // l1 = empty,  l2 = l, l = empty;
  101.   { l2.h = h;
  102.     l2.t = t;
  103.     l2.count = count;
  104.     h = t = 0;
  105.     count = 0;
  106.     return;
  107.    }
  108.  
  109.   if (h == 0) return;   /* empty list */
  110.  
  111.  
  112.   if (p->pred_link)
  113.   { l1.h = h;
  114.     l1.t = p->pred_link;
  115.     p->pred_link->succ_link = 0;
  116.    }
  117.  
  118.   p->pred_link = 0;
  119.   l2.h = p;
  120.   l2.t = t;
  121.  
  122.  
  123.   // have to set counters
  124.   // "count the smaller half" gives amortized n log n  bound
  125.  
  126.   obj_link* l = l1.h;
  127.   obj_link* r = l2.h;
  128.   int    c = 0;
  129.  
  130.   while (l && r)
  131.   { l = l->succ_link;
  132.     r = r->succ_link;
  133.     c++;
  134.    }
  135.  
  136.   if (l==0)   // left end reached first
  137.   { l1.count = c;
  138.     l2.count = count - l1.count;
  139.    }
  140.  
  141.   else
  142.   { l2.count = c;
  143.     l1.count = count - l2.count;
  144.    }
  145.  
  146.   /* make original list empty */
  147.   
  148.   h = t = 0;
  149.   count = 0;
  150.  
  151. }
  152.  
  153.  
  154. void obj_list::del(obj_link* x)
  155. { 
  156.   if (x==h)  
  157.     pop();
  158.   else
  159.     if (x==t)  
  160.        Pop();
  161.     else
  162.        { obj_link*  p = x->pred_link;
  163.          obj_link*  s = x->succ_link;
  164.          p->succ_link = s;
  165.          s->pred_link = p;
  166.          count--;
  167.         }
  168. }
  169.  
  170.  
  171. obj_link* obj_list::max(CMP_ITEM f) const
  172. { if (h==0) return 0;
  173.   obj_link* m=h;
  174.   obj_link* p=m->succ_link;
  175.  
  176.      while (p)
  177.      { if (f(p,m) > 0) m=p;
  178.        p=p->succ_link;
  179.       }
  180.  
  181.   return m;
  182. }
  183.  
  184. obj_link* obj_list::min(CMP_ITEM f) const
  185. { if (h==0) return 0;
  186.   obj_link* m=h;
  187.   obj_link* p=m->succ_link;
  188.  
  189.      while (p)
  190.      { if (f(p,m) < 0) m=p;
  191.        p=p->succ_link;
  192.      }
  193.  
  194.   return m;
  195. }
  196.  
  197.  
  198. void obj_list::apply(APP_ITEM apply)
  199. { register obj_link* p = h;
  200.   while (p)
  201.   { apply(p);
  202.     p = p->succ_link;
  203.    }
  204. }
  205.  
  206. void obj_list::permute()
  207. { 
  208.   obj_link** A = new obj_link*[count+2];
  209.   obj_link* x = h;
  210.   int j;
  211.  
  212.   A[0] = A[count+1] = 0;
  213.  
  214.   for(j=1; j <= count; j++)
  215.   { A[j] = x;
  216.     x = x->succ_link;
  217.    }
  218.  
  219.   for(j=1; j<count; j++)  
  220.   { int r = random(j,count);
  221.     x = A[j];
  222.     A[j] = A[r];
  223.     A[r] = x;
  224.    }
  225.  
  226.   for(j=1; j<=count; j++) 
  227.   { A[j]->succ_link = A[j+1];
  228.     A[j]->pred_link = A[j-1];
  229.    }
  230.  
  231.   h = A[1];
  232.   t = A[count];
  233.   
  234.   delete A;
  235. }
  236.         
  237.  
  238. void obj_list::bucket_sort(int i, int j, ORD_ITEM ord)
  239. { 
  240.   int n = j-i+1;
  241.  
  242.   register obj_link** bucket= new obj_link*[n+1];
  243.   register obj_link** stop = bucket + n;
  244.   register obj_link** p;
  245.  
  246.   register obj_link* q;
  247.   register obj_link* x;
  248.  
  249.   for(p=bucket;p<=stop;p++)  *p = 0;
  250.  
  251.   while (h) 
  252.   { x = h; 
  253.     h = h->succ_link;
  254.     int k = ord(x);
  255.     if (k >= i && k <= j) 
  256.      { p = bucket+k-i;
  257.        x->succ_link = *p;
  258.        if (*p) (*p)->pred_link = x;
  259.        *p = x;
  260.       }
  261.     else 
  262.        error_handler(4,"bucket_sort: value out of range") ;
  263.    }
  264.  
  265.  for(p=bucket; *p==0 && p<stop; p++);
  266.   
  267.  h = *p;
  268.  
  269.  if (h) 
  270.  { for(q=h;q->succ_link; q = q->succ_link);
  271.    h->pred_link = 0;
  272.    p++;
  273.   }
  274.  
  275.  while(p<stop) 
  276.  { if (*p)
  277.    { q->succ_link = *p;
  278.      (*p)->pred_link = q;
  279.      while(q->succ_link) q = q->succ_link;
  280.     }
  281.    p++;
  282.   }
  283.  
  284.  t = q;
  285.  
  286.  delete bucket;
  287. }
  288.  
  289.         
  290. void obj_list::quick_sort(obj_link** l, obj_link** r, CMP_ITEM usr_cmp)
  291. { // use parameter usr_cmp
  292.  
  293.   register obj_link** i = l+(r-l)/2; //random()%(r-l);
  294.   register obj_link** k;
  295.  
  296.   if (usr_cmp((*i),(*r))>0) SWAP(i,r);
  297.  
  298.   SWAP(l,i);
  299.  
  300.   obj_link* s = (*l);
  301.  
  302.   i = l;
  303.   k = r;
  304.  
  305.   for(;;)
  306.   { while (usr_cmp((*(++i)),s)<0);
  307.     while (usr_cmp((*(--k)),s)>0);
  308.     if (i<k) SWAP(i,k) else break;
  309.    }
  310.  
  311.   SWAP(l,k);
  312.  
  313.   if (k > l+MIN_D) quick_sort(l,k-1,usr_cmp);
  314.   if (r > k+MIN_D) quick_sort(k+1,r,usr_cmp);
  315. }
  316.         
  317.  
  318.  
  319. void obj_list::insertion_sort(obj_link** l, obj_link** r, obj_link** min_stop, 
  320.                                CMP_ITEM usr_cmp)
  321. {
  322.   register obj_link** min=l;
  323.   register obj_link** run;
  324.   register obj_link** p;
  325.   register obj_link** q;
  326.  
  327.   for (run = l+1; run <= min_stop; run++)
  328.       if (usr_cmp((*run),(*min)) < 0) min = run;
  329.  
  330.   SWAP(min,l);
  331.  
  332.   if (r == l+1) return; 
  333.  
  334.   for(run=l+2; run <= r; run++)
  335.   { for (min = run-1; usr_cmp((*run),(*min)) < 0; min--);
  336.     min++;
  337.     if (run != min) 
  338.     { obj_link* save = *run;
  339.       for(p=run, q = run-1; p > min; p--,q--) *p = *q;
  340.       *min = save;
  341.      }
  342.    }
  343. }
  344.  
  345.  
  346.  
  347. void obj_list::sort(CMP_ITEM f)
  348. { 
  349.   if (count<=1) return;    // nothing to sort
  350.  
  351.   obj_link** A = new obj_link*[count+2];
  352.  
  353.   register obj_link*  loc = h;
  354.   register obj_link** p;
  355.   register obj_link** stop = A+count+1;
  356.  
  357.   obj_link** left  = A+1;
  358.   obj_link** right = A+count;
  359.   obj_link** min_stop = left + MIN_D;
  360.  
  361.   if (min_stop > right) min_stop = right;
  362.  
  363. min_stop = right;
  364.  
  365.   for(p=A+1; p<stop; p++)
  366.   { *p = loc;
  367.     loc = loc->succ_link;
  368.    }
  369.  
  370.  
  371.    quick_sort(left,right,f);
  372.    insertion_sort(left,right,min_stop,f);
  373.  
  374.   *A = *stop = 0;
  375.  
  376.   for (p=A+1;p<stop;p++) 
  377.   { (*p)->succ_link = *(p+1);
  378.     (*p)->pred_link = *(p-1);
  379.    }
  380.  
  381.   h = A[1];
  382.   t = A[count];
  383.  
  384.   delete A;
  385. }
  386.  
  387.